/*
 * @lc app=leetcode.cn id=139 lang=javascript
 *
 * [139] 单词拆分
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const n = s.length;
  // s 的前 i 个字符是否可以被字典中的单词拼接出来。
  const curValidLen = Array.from({ length: n + 1 }, () => false);
  const wordSet = new Set(wordDict);
  curValidLen[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      // substring(start, end) 不包括end索引的字母，尾部全取s.(0,s.length)
      if (curValidLen[j] && wordSet.has(s.substring(j, i))) {
        curValidLen[i] = true;
        break;
      }
    }
  }
  return curValidLen[n];
};
// @lc code=end
